import functools


class Solution(object):
    def stoneGameII(self, piles):
        n = len(piles)
        for i in range(1, n):
            piles[i] += piles[i - 1]

        @functools.cache
        def search(start, m):
            max_val = - float('inf')
            if start + 2 * m - 1 >= n - 1:
                if start == 0:
                    max_val = piles[-1]
                else:
                    max_val = piles[-1] - piles[start - 1]
            else:
                for x in range(0, 2 * m):
                    if start == 0:
                        now_val = piles[start + x]
                    else:
                        now_val = piles[start + x] - piles[start - 1]
                    max_val = max(max_val, now_val - search(start + x + 1, max(x + 1, m)))
            return max_val

        a_val = search(0, 1)
        return (piles[-1] + a_val) // 2


data = Solution()
piles = [2, 7, 9, 4, 4]
print(data.stoneGameII(piles))